一些应用
P3769 [CH弱省胡策R2] TATT
原问题求解的是四维意义下的 LIS，容易想到先按第一维排序，然后转化为三维的偏序关系。
比较常规的解法是 cdq 分治套 cdq 分治优化 dp，但是这里采用 KD-Tree 来优化她。
按照第一维排序后，设 fif_ifi 表示当前以 iii 点为结尾的 LIS 长度最长是多少。有初始状态 fi=1f_i=1fi =1，转移方程形如：
fi=(maxxj≤xi,yj≤yi,zj≤zifj)+1f_i=(\max\limits_{x_j\le x_i,y_j\le y_i,z_j\le z_i}f_j)+1 fi =(xj ≤xi ,yj ≤yi ,zj ≤zi max fj )+1
考虑用数据结构优化。容易想到写一个树套树。注意到前面部分的查询其实就是在一个三维空间中查询最大值，然后添加 iii 位置就是在 KD-Tree 上单点插入。在每个结点上维护子树最大值信息，可以做到 O(n5/3)O(n^{5/3})O(n5/3) 解决该问题。
看上去比较吓人，但是 nnn 只有 500005000050000，而且 KDT 的时间复杂度跑不满，所以仍然可以无压力通过。
P5621 [DBOI2019] 德丽莎世界第一可爱
在上个题的基础上加了一个点的权值，只需要把上一题的 dp 初始条件修改为 fi=Cif_i=C_ifi =Ci ，转移方程修改为：
fi=(maxEj≤Ei,Aj≤Ai,Dj≤Difj)+1f_i=(\max\limits_{E_j\le E_i,A_j\le A_i,D_j\le D_i}f_j)+1 fi =(Ej ≤Ei ,Aj ≤Ai ,Dj ≤Di max fj )+1
按照 HHH 从小到大排序转移即可，需要大力卡常才能过。
P4848 崂山白花蛇草水
问题可以转化为矩形查询第 kkk 大值，矩形加。
看到查询第 kkk 大值容易想到用动态开点值域线段树维护，但是问题是在一个平面上的，也就是说普通的动态开点值域线段树已经无法维护。
因此容易想到树套树，即在动态开点值域线段树的每个结点上，都维护一个 K-D Tree。具体而言：
* 矩形加是简单的。
* 矩形查第 kkk 大可以在动态开点值域线段树上二分，对于当前值域线段树上的点 uuu，若其右儿子 rrr 对应的 K-D Tree 上当前矩形有 kkk 个点，那么就递归右子树，否则就递归左子树。
外层的动态开点值域线段树时间复杂度为 O(logV)O(\log V)O(logV)，内侧的 K-D Tree 时间复杂度为 O(n12)O(n^{\frac12})O(n21 )，因此总时间复杂度为 O(n32logV)O(n^{\frac32}\log V)O(n23 logV)。
下面这份代码曾经可以通过，找个时间再来卡常（）
P5471 [NOI2019] 弹跳
题意比较复杂，这里 copy 出一个简要题意：
> 给出二维平面上的 nnn 个整点 (xi,yi)(x_i,y_i)(xi ,yi )，满足 1≤xi≤w,1≤yi≤h1\le x_i\le w,1\le y_i\le h1≤xi ≤w,1≤yi ≤h。按给出顺序编号为 1,2,…,n1,2,\ldots,n1,2,…,n。有 mmm 次连边操作，每次操作给定 p,t,L,R,D,Up,t,L,R,D,Up,t,L,R,D,U，从结点 ppp 到满足条件 L≤xi≤R,D≤yi≤UL\le x_i\le R,D\le y_i\le UL≤xi ≤R,D≤yi ≤U 的所有这样的结点 iii 连接一条边权为 ttt
> 的有向边。求在所有连边操作结束后，从编号为 111 的点到其他点的最短路长度。
>
> Data Range: 1≤w,h≤n≤70000,1≤m≤150000,1≤ti≤100001\le w,h\le n\le 70000,1\le m\le 150000,1\le t_i\le 100001≤w,h≤n≤70000,1≤m≤150000,1≤ti ≤10000
题解：
先考虑一维的情况，此时连边操作形如让一个点 ppp 向一段区间 [l,r][l,r][l,r] 连边，容易发现这就是【模板】线段树优化建图。
扩展到二维，容易想到用 K-D Tree 来优化建图。具体的：
* 建立由这 nnn 个点组成的 K-D Tree，该树上有 nnn 个结点，令这些点对应过来的编号为 n+1,n+2,…,2nn+1,n+2,\ldots,2nn+1,n+2,…,2n 号。
* 对于一个点 ppp 向一个平面内所有点连边的情况，考虑直接遍历整棵 K-D Tree，对于当前所遍历到的结点 uuu 而言：
* 若 uuu 点子树对应的平面和查询的平面无交，那么不再递归，直接返回。
* 若 uuu 点子树对应的平面是查询平面的子集，那么直接从 ppp 点向 u+nu+nu+n 点连一条边权为 ttt 的有向边即可。
* 对于其余情况，特判掉 uuu 点自身所对应的坐标在查询平面内的情况，然后直接向左右子树暴力递归即可。
* 最后对于每个 i=1…ni=1\ldots ni=1…n，由 i+ni+ni+n 点向 iii 点连一条边权为 000 的有向边即可。
由 K-D Tree 的时间复杂度证明可知，这种方式建图会连 O(mn)O(m\sqrt n)O(mn ) 条边。因为 n≤70000n\le 70000n≤70000，所以该建边方法是可行的。此时如果直接显式建图，大约需要建 4×1074\times 10^74×107 条边，会爆内存。将上述做法改为隐式建图即可通过。
注：spfa 被卡了。
P12065 [THOI 2012] 森林旅店
邻域查询板子题，把前面的 P2093 和 P4148 合起来就可以过。
